﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<string>

//int main()
//{
//	string str("123456");
//	//使用迭代器区间初始化
//	vector<int> v(str.begin(), str.end());
//	//使用迭代器遍历
//	vector<int>::iterator it = v.begin();
//	while (it != v.end())
//	{
//		cout << *it - '0' << " ";
//		++it;
//	}
//	return 0;
//}

// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
//void TestVectorExpandOP()
//{
//	vector<int> v;
//	size_t sz = v.capacity();
//	v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
//	cout << "making bar grow:\n";
//	for (int i = 0; i < 100; ++i)
//	{
//		v.push_back(i);
//		if (sz != v.capacity())
//		{
//			sz = v.capacity();
//			cout << "capacity changed: " << sz << '\n';
//		}
//	}
//}

#include<iostream>
#include <string>
using namespace std;
int main()
{
	string s("hello");
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it;
		++it;
	}
	cout << endl;
	it = s.begin();
	while (it != s.end())
	{
		it = s.erase(it);
	}
	while (it != s.end())
	{
		cout << *it;
		++it;
	}
	return 0;
} 

class Solution {
public:
    string minWindow(string s, string t) {
        map<char, int> hash1, hash2;
        for (auto i : t)
            hash1[i]++;
        int min = INT_MAX, l = 0, r = 0;
        int len = t.size(), n = s.size();
        for (int left = 0, right = 0, cnt = 0; right < n; right++)
        {
            //进窗口
            hash2[s[right]]++;
            if (hash1.count(s[right]) && hash2[s[right]] <= hash1[s[right]])
                cnt++;
            //判断           
            while (cnt == len && (hash1.count(s[left]) == 0 || hash2[s[left]] > hash1[s[left]]))
                hash2[s[left++]]--; //出窗口
            //更新结果
            if (cnt == len && min > right - left + 1)
            {
                l = left, r = right;
                min = r - l + 1;
            }
        }
        return min == INT_MAX ? "" : s.substr(l, min);
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return _search(nums, 0, nums.size() - 1, target);
    }

private:
    int _search(vector<int>& nums, int left, int right, int target) {
        if (left > right)
            return -1;
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] > target)
            return _search(nums, left, mid - 1, target);
        else if (nums[mid] < target)
            return _search(nums, mid + 1, right, target);
        return 0;
    }
};